/**
 * 
 */
package leetCode;

import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

/**
 * @author zhong
 *
 */
public class MinimizeMaxDistancetoGasStation {
	class Duan implements Comparable<Duan> {
		double total;
		double each;
		int count;

		public Duan(double t) {
			each = total = t;
			count = 1;
		}

		public void splite() {
			count++;
			each = total / count;
		}

		@Override
		public int compareTo(Duan o) {
			double d = this.each - o.each;
			if (d < 0) {
				return -1;
			} else if (d > 0) {
				return 1;
			}
			return 0;
		}

	}

	/**
	 * 超时了
	 * 
	 * @param stations
	 * @param K
	 * @return
	 */
	public double minmaxGasDist(int[] stations, int K) {
		Arrays.sort(stations);
		PriorityQueue<Duan> queue = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < stations.length - 1; i++) {
			queue.add(new Duan(stations[i + 1] - stations[i]));
		}
		for (int i = 0; i < K;) {
			Duan d1 = queue.poll();
			Duan d2 = queue.poll();
			do {
				d1.splite();
				i++;
			} while ((d1.each > d2.each) && i < K);
			queue.offer(d1);
			queue.offer(d2);
		}
		return queue.poll().each;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] stations = { 10, 19, 25, 27, 56, 63, 70, 87, 96, 97 };
		int K = 3;
		// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
		// 9
		// 10,19,25,27,56,63,70,87,96,97
		// 3
		//
		System.out.println(new MinimizeMaxDistancetoGasStation().minmaxGasDist(stations, K));
	}

}
